/*
 * @Descripttion: 
 * @version: 
 * @Author: lily
 * @Date: 2021-04-13 11:32:13
 * @LastEditors: lily
 * @LastEditTime: 2021-04-15 16:03:51
 */
/*
 * @lc app=leetcode.cn id=39 lang=javascript
 *
 * [39] 组合总和
 */

// @lc code=start
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

//  思路：回溯法
//  有约束的选择元素
//  如果当前所选元素和 === target，加入res
//  如果当前所选元素和  >  target，剪枝
//  通过限制下一次选择的起点 来防止组合的重复
//  https://leetcode-cn.com/problems/combination-sum/solution/shou-hua-tu-jie-zu-he-zong-he-combination-sum-by-x/

//  复杂度：O(S)，S 为所有可行解的长度之和。 O(target)

var combinationSum = function (candidates, target) {
    let res = []
    // start是当前选择的起点索引 curArr是当前的集合 sum是当前求和
    var dfs = (start, curArr, sum) => {
        if (sum >= target) {
            if (sum === target) {
                // 利用slice返回新数组进行深拷贝 这里不能直接使用curArr
                res.push(curArr.slice())
            }
            // 结束当前递归
            return
        }
        // 枚举当前可选的数，从start开始
        for (let i = start; i < candidates.length; i++) {
            // 选这个数
            curArr.push(candidates[i])
            // 基于此继续选择，传i，下一次就不会选到i左边的数
            dfs(i, curArr, sum + candidates[i])
            // 撤销选择，回到选择candidates[i]之前的状态，继续尝试选同层右边的数
            curArr.pop()
        }
    }
    // 最开始可选的数是从第0项开始的，传入一个空集合，sum也为0
    dfs(0, [], 0)
    return res
};
// @lc code=end

console.log(combinationSum([2, 3, 5], 8));